
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def merge(a, b):
            head = ListNode()
            cur = head
            while a and b:
                if a.val <= b.val:
                    cur.next = a
                    a = a.next
                else:
                    cur.next = b
                    b = b.next
                cur = cur.next
            if a:
                cur.next = a
            if b:
                cur.next = b
            return head.next

        def helper(lists):
            result = []
            for i in range(0, len(lists), 2):
                if i + 1 < len(lists):
                    result.append(merge(lists[i], lists[i+1]))
                else:
                    result.append(lists[i])
            return result
        if len(lists) == 0:
            return None
        while len(lists) > 1:
            lists = helper(lists)
        return lists[0]

if __name__ == '__main__':
    print(Solution().mergeKLists([]))
    print(Solution().mergeKLists([[]]))
    print(Solution().mergeKLists([
        ListNode(1, ListNode(4, ListNode(5))),
        ListNode(1, ListNode(3, ListNode(4))),
        ListNode(2, ListNode(6)),
    ]))